import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @创建人 luoxiang
 * @创建时间 2020/10/28  10:09
 * @描述 146. LRU 缓存机制       https://leetcode-cn.com/problems/lru-cache/#/
 */
public class LeetCode_146_2 {

    static class DoudleList {
        int key;
        int value;
        DoudleList prev;
        DoudleList next;

        public DoudleList() {
        }

        public DoudleList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    static class LRUCache {

        private Map<Integer, DoudleList> cache = new HashMap<Integer, DoudleList>();
        private int size;
        private int capacity;
        private DoudleList head, tail;

        /**
         * 初始化
         * 容量大小，当前的 size 大小
         * 伪头节点 ， 伪尾节点
         * @param capacity
         */
        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头节点和伪伪节点
            this.head = new DoudleList();
            this.tail = new DoudleList();
            this.head.next = this.tail;
            this.tail.prev = this.head;

        }

        /**
         * 从 HashMap 里面通过 key 来获取，时间复杂度为 O(1)
         *
         * @param key
         * @return
         */
        public int get(int key) {
            DoudleList node = this.cache.get(key);
            if (node == null) { // 再 map 里面没有找到，返回 -1
                return -1;
            }
            // 在 map 当中找到了，将当前节点 移动到 最前面
            moveToHead(node);
            return node.value;

        }

        /**
         * 1、先 判断 key 对应的 节点是否存在
         * 存在： 1、更新 value ; 2、并将节点移动到 最前面
         * 2、不存在，创建一个新的节点， DoubleList(key,value)
         * 在最前面插入一个新的节点，size ++,在 map 加入缓存
         * 判断 缓存是否已满
         * 已满，删除最后一个节点,size --,在 map 移除缓存
         *
         * @param key
         * @param value
         */
        public void put(int key, int value) {
            DoudleList node = cache.get(key);
            if (node != null) {
                node.value = value;
                moveToHead(node);
            } else {
                DoudleList newNode = new DoudleList(key, value);
                cache.put(key, newNode);
                addToHead(newNode);
                size++;
                if (size > capacity) { // 说明已满
                    DoudleList tail = removeTail(); // 删除最后一个节点
                    cache.remove(tail.key);
                    size--;
                }
            }
        }

        /**
         * 增加到第一个节点，头节点之后
         *
         * @param node
         */
        private void addToHead(DoudleList node) {
            // 当前节点的 前指针 ——> head
            node.prev = head;
            // 当前节点的 后指针 ——> head.next
            node.next = head.next;
            // head.next ，头节点的下一个节点 的前指针 ——> node
            head.next.prev = node;
            // 头节点的后指针 ——> node
            head.next = node;
        }

        /**
         * 删除某一个节点
         */
        private void removeNode(DoudleList node) {
            // 当前节点的 上一个节点 的后指针 ——> 当前节点的 后指针
            node.prev.next = node.next;
            // 当前节点的 下一个节点 的前指针 ——> 当前节点的 前指针
            node.next.prev = node.prev;
        }

        /**
         * 删除当前节点
         * 并添加到第一个节点
         */
        private void moveToHead(DoudleList node) {
            removeNode(node);
            addToHead(node);
        }

        /**
         * 删除最后一个节点
         * 1、根据 伪尾节点 删除上一个节点
         */
        private DoudleList removeTail() {
            DoudleList node = tail.prev;
            removeNode(node);
            return node;
        }


    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回  1
        cache.put(3, 3);    // 该操作会使得关键字 2 作废
        cache.get(2);       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得关键字 1 作废
        cache.get(1);       // 返回 -1 (未找到)
        cache.get(3);       // 返回  3
        cache.get(4);       // 返回  4

    }


}
